package com.xgb.edu.String;

import java.util.LinkedList;

/**
* KPM算法实现
* @author xiaowu
* E-mail:865815412@qq.com
* @version 创建时间：2018年12月8日 下午4:12:32
*/
public class KPMString {
	static int[] next  = new int[20];
	
	static LinkedList<String> link;

	public static int indexOf(java.lang.String target,java.lang.String pattern){
		return indexOf(target, pattern, 0);
	}
	
	public static int indexOf(java.lang.String target,java.lang.String pattern,int begin){
		int n = target.length(),m = pattern.length();
		//对begin容错
		if(begin < 0)
			begin = 0;
		//如果目标字符串长度为0，或者目标字符串长度比匹配的字符串小或者begin开始位置比目标字符串长度大，算法直接返回-1
		if(n == 0 || n < m || begin >= n)
			return -1;
		int i = begin,j = 0;//i , j 分别为目标串、模式串比较字符串下标
		while(i < n && j < m){
			if(j == -1 || target.charAt(i) == pattern.charAt(j)){ //若当前两个字符相等，则继续比较后续字符
				i ++;
				j ++;
			}else{
				j = next[j];
				if(n-i+1<m-j+1){
					break;
				}
			}
		}
		
		//匹配成功
		if(j == m)
			return i + j;
		return -1;
		
	}
}
